package lanqiao._02算法训练.page01;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
 * 　　例如:
 * 　　3 1 2 4
 * 　　4 3 6
 * 　　7 9
 * 　　16
 * 　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
 * 输入格式
 * 　　第1行为两个正整数n，sum
 * 输出格式
 * 　　一个1～N的一个排列
 * 样例输入
 * 4 16
 * 样例输出
 * 3 1 2 4
 *
 * 思路：
 * 求全排列，检查是否符合，只输出第一结果
 * @since 2022 - 10 - 28 - 23:33
 */
public class _03数字游戏 {
}
class Main3_0{
    static int n;
    static int sum;
    //保证输出一个结果
    static boolean hasFounded = false;
    //visited[i] 表示 i 是否使用过
    static boolean[] visited;
    //存放枚举排列
    static int[] nums;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sum = sc.nextInt();
        visited = new boolean[n + 1];
        nums = new int[n];
    }
}
class Main3{
    static int n;
    static int sum;
    //保证输出一个结果
    static boolean hasFounded = false;
    //visited[i] 表示 i 是否使用过
    static boolean[] visited;
    //存放枚举排列[全排列]
    static int[] nums;
    static void dfs(int index){
        if(hasFounded) return;
        if (index == n){    //一个排列情况
            //检查是否是符合情况的排列
            int[] nums2 = Arrays.copyOf(nums, n);
            System.out.println(Arrays.toString(nums));
            //累加规则
            for(int i = 0; i < n - 1; i++){
                for(int j = 0; j < n - i - 1; j++){
                    nums2[j] += nums2[j + 1];
                }
            }
            //符合
            if(nums2[0] == sum){
                for(int i = 0; i < n; i++) System.out.print(nums[i] + " ");
                hasFounded = true;
            }
            return;
        }
        // 每个数 [1-n]
        for(int i = 1; i <= n; i++){
            if(!visited[i] && !hasFounded){
                visited[i] = true;
                nums[index] = i;
                dfs(index + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sum = sc.nextInt();
        visited = new boolean[n + 1];
        nums = new int[n];
        dfs(0);
    }
}
/*
优化检测合法情况
3 1 2 4
4 3 6
7 9
16
分解每个数
3 1 2 4

3 1 1 2 2 4 //4 3 6

3 1 1 2 1 2 2 4 //7 9
sum = c30 * 3 + c31 * 1 + c32 * 2 + c33 * 4
得到公式：
t = n - 1
sum = ct0 * nums[0] + ct1 * nums[1] + ... + ctt * nums[t]
排列组合的递推公式：
cnm = cn-1 m + cn-1 m-1
 */
class Main3_1{
    static int n;
    static int sum;
    //保证输出一个结果
    static boolean hasFounded = false;
    //visited[i] 表示 i 是否使用过
    static boolean[] visited;
    //存放枚举排列
    static int[] nums;
    //排列组合递推
    static int[][] c;
    static void dfs(int depth){
        if(hasFounded) return;
        if (depth == n){    //一个排列情况
            //检查是否是符合情况的排列
//            //累加规则
//            for(int i = 0; i < n - 1; i++){
//                for(int j = 0; j < n - i - 1; j++){
//                    nums2[j] += nums2[j + 1];
//                }
//            }
            //优化
            int total = 0;
            int t = n - 1;
            for(int i = 0; i < n; i++){
                total += c[t][i] * nums[i];
            }
            //符合
            if(total == sum){
                for(int i = 0; i < n; i++) System.out.print(nums[i] + " ");
                hasFounded = true;
            }
            return;
        }
        // 每个数 [1-n]
        for(int i = 1; i <= n; i++){
            if(!visited[i] && !hasFounded){
                visited[i] = true;
                nums[depth] = i;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sum = sc.nextInt();
        visited = new boolean[n + 1];
        nums = new int[n];
        /*
        t = n - 1
        只需要 ct0 到 ctt
        n行n列即可
         */
        c = new int[n][n];
        //cii = 1 ci0 = 1
        for(int i = 0; i < n; i++){
            c[i][0] = c[i][i] = 1;
        }
        //cmn = cm-1 n + cm-1 n-1
        for(int i = 1; i < n; i++){
            for(int j = 1; j < i; j++){
                c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
            }
        }
//        for(int[] cc : c){
//            System.out.println(Arrays.toString(cc));
//        }
        dfs(0);
    }
}